The present invention relates generally to encryption, and more particularly, to an encryption system in which the plaintext and the raw cipher are different lengths and to a denial featured cryptography. Additional applications include pattern recognition, and other situations in which one modifies the inferential visibility of data.
Cryptographic systems have evolved along deeply seated xe2x80x9cgroovesxe2x80x9d: idiosyncracies. Mainly:
1. To express messages with a simple alphabet.
2. To render a message hard to read by creating a message form (cipher) which is expressed with the same or similar alphabet as the original message, and of the same size, or of fixed ratio vs. the original message.
Human languages are expressed with an alphabet which for most languages is limited to two to three dozen symbols. Cryptographers have embraced this paradigm, and thereby limited their process to ways by which a certain sequence of letters can be written in a different sequence (usually of the same alphabet), in a way that would confuse the unintended readers, but will allow the intended readers to use a reverse process (decryption) to uncover the original message which is assumed to be plain and readily understood.
Thus, the profound emotional expression of love can be expressed in English with its 26 letters as a statement:
I LOVE LUCY
which is readable to all English readers, (making it difficult to comprehend for people not conversant with Englishxe2x80x94alas, that is not an aspect of formal cryptography, as defined above). To establish discrimination between those designated as intended readers, and the rest of the English speaking public, the same alphabet is typically used (same 26 letters), but an encryption process would transform the message to, say:
JKOCXNGHL
The process that leads from the original message (as it reads before the formal encryption takes it on), to the cipher has also fallen into a deep groove of conservatism. It is carried out in a mathematical process that requires another input, called xe2x80x9ckeyxe2x80x9d or encryption key, Ke. And the respective idiosyncratic maxim says:
3. Ke should be as small as possible.
The intended reader, so the paradigm premise says, has his or her own key, a reading key or decryption key Kd which together with the cipher serves as an input to a decryption algorithm that uncovers the original message M. Kd is often the same as Ke (Kd=Ke) but not necessarily so. At any rate, Kd also submits to the smallness maxim:
4. Kd should be as small as possible.
The published consensus of the profession has also subscribed to:
5. Kerckhoff Law: which states that a good cryptographic system is one in which everything is fully exposed except the very identity (not the format) of the decryption key Kd, which too is expected to be a selection among a finite well known possibilities.
The term xe2x80x9cpublished consensusxe2x80x9d warrants some elaboration. Cryptography is unique in as much as its maximum benefit is achieved when its achievements are left undisclosed. Furthermore, a would be cryptanalyst (code-breaker)xe2x80x94an unintended reader in our terminologyxe2x80x94has a lot to gain by convincing cryptographic message writers that he or she can not read ciphers constructed with a certain encryption algorithm, which in fact the code breaker can xe2x80x9cbreakxe2x80x9d. If the message writer believes it, he or she would aggregate the important secrets into that cipher-paradigm, thereby helping the cryptanalyst. The latter will not only be able to read the sensitive secrets of the message writers, he or she would also enjoy a distinct selection between what is sensitive and secret, and what is not. This is because the gullible message writer is likely to point to his or her secrets by the very fact that he or she would encrypt them. It is an irony that in such cases, it is better not to encrypt anything, and thereby achieve some protection by xe2x80x9cdrowningxe2x80x9d the secrets within reams of innocuous information. For these reasons there emerged a big gap between what is officially said, and published on the matter, and what is actually happening in the clandestine ditches where the battle for timely knowledge rages with great zeal and some unbecoming side effects. Therefore, unlike the case with other fields of science, one should be rather apprehensive in regarding the xe2x80x9cpublished consensusxe2x80x9d.
One enlightened way to review the previous art is to use the historic time-line. We may discern several distinct eras:
1. Antiquity up to WW-I.
2. WW-II encryption.
3. Electronic Computing Era.
4. The era of the information superhighway. (Internet).
Antiquity up to WW-I
Up to WW-I formal encryption was based on changing messages written in Latin or prevailing alphabet by creating a message of equal size (in most cases), with the same alphabet. The changes were of two types: transposition and substitution: changing the order of the letters, or replacing each letter with another. The result looked so confusing that only determined mathematicians even tried to break those ciphers. Yet, for those mathematicians it was usually a matter of patience.
In most cases in this era the substitution process was fixed per letter; that is if the letter g was substituted by k in one appearance, it was substituted by k for all other appearances. This type is named monoalphabetic substitution. The term is a bit misleading. The xe2x80x98monoxe2x80x99 attributes suggests that for each substituted letter the substituting letter is always the same. The xe2x80x98alphabeticxe2x80x99 attribute suggests that the encryption happens through fiddling with alphabet.
Monoalphabetic substitution encryption has a gripping charm, perhaps because on one hand it appears so unsolvable, and on the other hand it just about always yields to patient amateur attacks. The fact is that even today when monoalphabetic substitution is obsolete for any serious business, it is live and well in the world of entertainment, and a large variety thereof is found in form of puzzles, riddles in most respected dailies and magazines.
That charm of simple alphabetic substitution sank this mode into the consciousness of the craft, and determined its further development for centuries. Encryption as it developed remained locked into this basic premise; adding, over the years, two modes of complexity (identified herewith, discussed below)
1. Homophonic substitution
2. Polyalphabetic substitution
The object of those complexities was to throw as many obstacles as possible on the path of understanding against the unintended readers.
A paradigm developed. The writer puts his message into ordinarily language writing, using the common alphabet (26 letters in English). That writing is called the plaintext; suggesting it is plainly understood. The encryption was limited to changing the plaintext to a message which was expressed with the same alphabet (26 letters in English) but its appearance was different enough from the plaintext that the latter would not be easily discovered. This hard to understand message form was called ciphertext, or simply: cipher.
The homophonic complexity, (not a very telling name), was comprised of mapping a single letter into two or more letters. Instead of mapping j to y, one mapped j to uyr. This tripled the size of the message in its cipher form, but kept the ratio between the plaintext message (before the encryption) and the cipher (after the encryption) fixed, which means that once the method was identified, the cipher length betrayed the plaintext length.
The polyalphabetic variety, was a one-to-many option in terms of replacing the same plaintext letter with a different (or same) letter each time. That is, k would become p on one appearance, c on another, n on the third etc. This variety turned out as the most serious avenue for encryption development for years to come. The big question was how to build such a mapping variety. In the monoalphabetic case one needed only a simple table that would match a plaintext letter with a cipher letter. But if a can be b on one occasion, c on another, d, e, f . . . including axe2x80x94on different occasions then clearly there must be something else other than the identity of the plaintext letter that would dictate which is the letter to map into (the replacing letter). That something else could be:
The rest of the plaintext
The rest of the ciphertext
Additional informationxe2x80x94neither the plaintext, nor the ciphertext in any combination. A rich mathematical variety was developed to create increasingly complex combinations, and this trend lingers today.
That variety (of polyalphabetic complexity) may be cast as:
1. Polygram encryption
2. Order driven encryption
3. Hitherto encryption
4. xe2x80x9cfull-restxe2x80x9d encryption
1. Polygram encryption: In a polygram the substitution choice for a given letter depends on its immediate neighbors. The plaintext letters are being taken 2, 3 or more at a time and the substitution is based on the identify of these groups. Thus AB would become GH and AC would turn up as UK, (in a 2-gram substitution).
2. Order driven encryption: The replacement choice for a given letter was based on its position as counted from the beginning of the plaintext. For most cases this was periodic, meaning that the rules to replace a letter at position i (i=1,2, . . . ), was the same as for the letter in position j where ti j=i +k*p
where k=1,2,3, . . . and p is an integer called a period.
3. Hitherto Encryption: In this variety the rules to replace a given letter were based on what happened in the encryption process up to that point the xe2x80x9chithertoxe2x80x9d information could have been within the plaintext letters up to that point, or within the developing ciphertext up to that point, or a combination thereof.
4. xe2x80x9cFull Restxe2x80x9d encryption: This variety, widely considered the most complex, says that the replacement choice for a given letter would be determined by the rest of the plaintext, the letters beforehand, and the letter to follow. This option was too difficult to implement prior to the introduction of electronic computing.
The centuries of encryption prior to WW-II showed a distinct consolidation around the polyalphabetic procedure, gradually pushing all other methods into the shadows of the non-published, non discussed category. Few stories survived, but no one knows how many were lost, or how extensive the imaginative non conservative encryption was, and what was its role in human history. In most cases the non alphabetic options were based on graphics.
The growing strength and complexity of encryption procedures had an important impact. It downgraded the art and science of secret writing (steganographyxe2x80x94the practice in which one hides the very existence of a message, rendering it unnecessary to decrypt it). Perhaps the reason is that hiding message existence was more an art, and less regimented, less mathematical, less provable, less repeatable than encryption. Psychologically the encryption designer thumbs his or her nose at the unintended reader saying: Try this! who is a better mathematician? In message hiding there is no xe2x80x9cin your facexe2x80x9d boasting.
To further understand the world of encryption in previous centuries and its impact on today""s practice it is necessary to bring up the aspect of hostility zones.
Hostility Zones
In an encryption situation the discrimination between the intended reader and the unintended reader happens by exchanging information between the writer and the intended reader in a zone or an environment which is considered safe, or hostility-free. Hostility here is expressed by the eavesdropping capability of unintended readers. The prevailing paradigm was that minimum information is exchanged in the hostility-free zone. But that little information should allow a safe exchange of even a large volume of information carried out in the hostile zone. Safe exchange means that the hostile unintended readers would not be able to decipher without crossing a threshold of xe2x80x9ccrackingxe2x80x9d effort. Why such a paradigm? Because this allows for two people to exchange minimum information at a given time in a hostility-free zone, and then exchange future information in large quantities in hostile areas; that is information which is not available while the two are talking safely. This premise is identical to the above mentioned notion of small keys. In fact the information which is exchanged in safety between the writer and the intended reader is the method to be used for the encryption, and the key (which is by definition all the information exchanged in hostility free zone, other than the method itself).
Historically it was considered safest to commit the key and of course, the method to memory, so encryption professionals were driven to devise smaller and smaller keys that would provide better and better security (stronger discrimination between the intended and the unintended reader).
In response, cryptanalysis, (the effort to break a cipher, to become a successful unintended reader), was focused on discovering that key. Since the key was smaller than the plaintext, there was a smaller field to search for it, and hence the better the chances.
Up until World War II, the small key monoalphabetic, then polyalphabetic ciphers were in vogue. Code breaking consisted of a systematic exhaustive examination of possibilities, employing mathematics, injected with a large body of clues and support data. These clues were part public information that was compiled to useful parameters, e.g. the frequency of letters in a given language, the frequency of words, or the frequency of words which have two or more of the same letter etc. The other part was case dependent. If the unintended reader knows who the writer and the intended reader are, he can surmise what the plaintext message could be, and use this information to accelerate the exhaustive search for the answer (the plaintext).
Throughout the pre-WW-II era and beyond, unintended readers enjoyed two crucial advantages in their attempt to read encrypted messages:
1. They generally knew which method was used.
2. They knew when they xe2x80x9cgot itxe2x80x9d (when the cryptanalysis was successful).
Acting as a shadowy cult, the encryption practitioners have been communicating with each other in conferences, publications and personal communication. In Europe where this tradition was most developed, friends became foes, and foes became friends with the frequent change of political winds, and so code breakers of one country had a pretty good idea of the mind set and the method used by their now opponents. Since most encryption practice was military oriented, the methods in use were officially documented and largely distributed. This made it very common for code books, and code officers to fall into enemies hands, betraying at the very least the method in use. And since it was deemed cumbersome and onerous to change a method, compared to changing the key, the latter was the option of choice. Later on, Kerckhoff, a Dutch encryption professional, formulated his law that states that encryption procedure must be thoroughly tested, and thus it must be made public, and eventually carry its full secrecy value and right in the identity of the key itself.
The other, perhaps the most important advantage for code breakers was the fact that the methods used were such that there was no confusion as to whether or not the code breaker arrived at his coveted targetxe2x80x94the plaintext. It was statistically unlikely that more than one reasonable message would be converted to the same ciphertext. In other words, knowing the method in use, and having even a slightly different key than what was actually used, would create a meaningless plaintext which was clearly not it. This, in and by itself, would offer a critical feedback to the code breaker. He would know when to try again. And if and when the plaintext would emerge as a meaningful message, expected of the known writer, then there would be that important signal that the job was donexe2x80x94the code broken. Having only one plausible solution to a cipher is prevalent in today""s practice. Mathematically:
Using any polyalphabetic encryption method or close variety thereof, E, for which the corresponding decryption algorithm is D; if plaintext M turned into cipher C by employing encryption keys K=Ke=Kd, then it is highly unlikely that there is another key Kxe2x80x2xe2x89xa0K such that by decrypting C with Kxe2x80x2 it would yield plaintext Mxe2x80x2xe2x89xa0M, in such a way that Mxe2x80x2 would be interpreted as the original message, M.
Overall the role of encryption prior to World War I was not extremely critical. Message hiding was arguably more important and more productive. And the question of who won, the code breakers, or the code writers is too dependent on arbitrary definitions of winning and losing. Alas, in World War One a single instance of code breaking changed world history. An encrypted cable written by the German foreign minster, Zimmerman, to his ambassador in Washington, was broken by British intelligence who forwarded the plaintext to Woodrow Wilson, the American President, and the resulting anger plunged the US into the war. Otherwise, the isolationists pull would likely have prevailed, Germany would have had a good chance to win World War One, and the history of the world have been quite different.
This single instance created shock waves world wide, and since then encryption was no longer a shadowy craft known and minded by esoteric few, but rather a make-it-or-break-it factor in prime time world affairs. And it has been like that ever since.
The Zimmerman turning point also indicated that even if only a tiny fraction of encrypted messages is being crackedxe2x80x94the impact may be world dramatic. When World War II came around, all the belligerent countries took encryption to new heights, using the best technology of the day to devise more and more complex ciphers, and to break the same.
The World War Two Encryption Era
Using electro mechanics, a combined feat of mathematics and engineering produced cipher machines which employed newly complex polygraphic encryption. The basic procedure was curiously similar through the belligerent forces of the second world war. The American Sigaba, the British Typex, the Japanese Purple, and the German Enigma all use a large key which is derived from a smaller key, and while it looks random, it is not, and to that extent it is vulnerable to attack. The annals of this greatest human tragedy indicate that these electro mechanical polygraphic cipher machines were highly breakable under the relentless war effort of the respective code breakers. The Germans broke the British merchant code; Enigma and Purple yielded to the allies. The impact of these broken code was substantial, many lives have been saved, many have been lost on that account, and arguably the war could have turned up differently without these mathematical feats. Having used the adjective xe2x80x98mathematicalxe2x80x99, it is worth noting, that in all cases, a substantial non-mathematical factor was playing a pivotal role. The electro mechanical devices were captured, people talked, and psychological warfare weighed in heavily.
Two characteristics of WW-II encryption are retrospectively important:
1. Low volume per analyst
2. Developing encryption mathematics and formal complexity assessment
A German U-boat would pop out its antenna and spurt a short message to headquarters. The message would be radio captured and then become fodder for thousands of British analysts in Bletchely Park near London, all working on reading the code, using purloined enigma machines.
A large cadre of mathematicians have sharpened their WW-II pencils on advancing a previously sleepy branch of mathematics: number theory. Prior to the war, one mathematician, Fermat, would propose a theorem, (the Fermat theorem) in 1640, Euler would offer a proof in 1736xe2x80x94a century later. In the war number theory was combined with statistical analysis and engineering to actually compute how difficult would it be for the unintended reader to read the plaintext.
Encryption mathematics was expressing the fundamental tenet of the prevailing encryption mode: letter-for-letter in a polyalphabetic fashion. The respective mathematical tool was module mathematics: a mathematical analysis in which any large series of numbers is mapped (matched) to a relatively small, fixed set. Any large as desired integer L is mapped to one of the numbers 1 to n, by dividing it by n, and matching it with the remainder, r:
L=k*n+r
where k is any integer, and 0xe2x89xa6rxe2x89xa6(nxe2x88x921). Gauss in 1801 expressed this matching through the congruence symbol (which we shall here use interchangeably with xe2x80x9c=xe2x80x9d, where no confusion may arise).
L=r (mod n)
The mathematics of encryption would nominally use n=26 for the 26 letters in the nominal English alphabet, and propose complicated algorithms to manipulate large numbers which would then be matched to a letter of the alphabet through module mathematics.
Module mathematics and letter for letter encryption would stay in the main stream for decades after the war. It was clear, elegant, and it offered a very practical advantage: it lent itself to product encryption.
Product Encryption
Product encryption is by definition encryption of encryption. Intuitively, if one takes a cipher and runs it again into the same, similar or dissimilar encryption cycle, then the outcome would be xe2x80x98further awayxe2x80x99 from the plaintext. By repeating the process once more, and again, one, arguably, would increase the xe2x80x98decryption mileagexe2x80x99, making it more difficult to break. In pre WW-II era product ciphers were desirable but not too practical because of the manual burden they imposed on the intended reader. The intuitive desirability of product ciphers locked in the letter for letter paradigm, because only by keeping that paradigm would it be possible to take a cipher and treat it as a plaintext to create another cipher, and then repeat the process again and again.
On second thought, product cipher is an expression of weakness. It acknowledge the ease of breaking a single decryption cycle. Alternatively put: the better the encryption, the less it would benefit from recycling.
The critical legacy of the war was that additional complexity was needed to build secure ciphers, and to crack opponent""s codes. It also manifested the role of non mathematical input into the code breaking art, and from that time on, each country has sunk in fortunes and nurtured a cadre of its most brilliant mathematical minds in waging the war of secret codes.
The Electronic Computer Era
The electronic computer emerging after the second world war, has become the indispensable tool of modern cryptography. It allowed complex crypto system design, and equally complex cryptanalysis. The legacy of the great war was that mathematics wins. And so in parallel with the increasing computing power, a tidal wave of mathematical research has thrust the field into its present state. The implicit fundamental assumption of the various methods today is embodied in the claim that all the unintended readers suffer from explicit mathematical ignorance. Specifically, the attacking cryptanalysis is not smart enough to figure out a way to accelerate the brute force search (exhaustive search for all possible keys). Such dumb crypt analysts are assumed to use the fastest computers available to them, and thus a figure of how long it would take those analysts to break the code is so often pronounced as a proof of cipher resistence. It is a fundamental weakness, which for some borders at mathematical pomposity: a mathematician saying: I tried to find mathematical insight to break the cipher, and failed. Ergo: everybody else will certainly fail!
The only proposed crypto system which is mathematically secure, is the one known as the infinite key, or one-time pad, which is considered impractical in its pure implementation.
In a bird""s view modern cryptography is based on complex algorithms fed by the plaintext and the xe2x80x9ckey;xe2x80x9d spewing a ciphertext as large as the plaintext. The prevailing methods use a binary sequence as a key. The first distinction is with respect to its length:
large keys
small keys
Large Key Cryptography
In its extreme case the key is as long as the message itself. (This is the infinite key method mentioned above). This equal length removes the key from the status of being the weakest link, or the crypt analytical target. A key as long as the message itself no longer contains less uncertainty than the message it encrypts. As a matter of fact, the equal length key can be made less attractive than the message by producing it as a random sequence, where as the plaintext message suffers from the idiosyncracies of the human language.
One simple implementation of this large-key method is as follows:
1. Write a plaintext, (P), as a binary sequence of length L bits.
2. Generate a key, (k), of length L random binary digits. 3. Process P and k as a bit-by-bit exclusive-or (XOR), to yield an L-bits long cipher, C.
The practical question is how to transport the long key to the intended readers. If an L size key is generated at a certain time point, and shared with an intended reader, then the writer-reader will enjoy a mathematically secure system that would be good for an L-bits long message. For additional communication, more key-bits must be generated, and shared. This burden diminishes the practicality of this paradigm. Most of the practical users have retreated to small size keys.
Small Size Keys, Computing-era Cryptography
These methods are divided into three categories:
1. Pseudo-random long key generators.
2. Symmetric short keys
3. Asymmetric short keys
The first category is an attempt to employ a long key that would pass for a long random sequence. The idea is to employ an algorithm that would use a short key as part or all of its input, and then generate an unending sequence that would be as close as possible to a true random series. This theoretically attractive method is not very popular arguably because, it is difficult to ascertain a mathematical measure of its vulnerability. Mathematically, the longer the message that is encrypted with that pseudo-random key, the more distinct its patternxe2x80x94it""s distance from pure randomness (a vague concept anyway). Say then, that pseudo-random long keys, or as they are commonly called, stream ciphers, suffer from increased vulnerability proportional to volume and usage. The more popular methods, discussed below, appear to be of fixed vulnerability, measurable through time to cryptanalyze. These measurements, as claimed above, rely on the implicit assumption of mathematical ignorance.
The prevailing cryptography is based on fixed-size small keys which will resist a timely brute force analysis, and which are based on algorithms that would defeat any attempt to accelerate that brute force cryptanalytic strategy. As outlined above these methods are either of the symmetric type, or the asymmetric type. Symmetry means that decryption is carried out essentially as a step by step reversal of the step wise encryption process. Asymmetry means that decryption is sufficiently different from encryption. In both cases the combined encryption-decryption process should reproduce the plaintext. But in the symmetric case it is akin to taking a trip from point A to point B, and then returning through the same track, while in the asymmetric case, the trip back to A, takes a completely different route. In the symmetric case one must hide the encryption process since it exposes the decryption route. In the asymmetric case the encryption can be made public, since the way back to the plaintext is sufficiently different, mathematically speaking.
Symmetric Key Computing Era Cryptography
This paradigm calls for a fixed size key to be shared by writers and readers alike. That key, until changed, would be used for writing secret messages and for reading the same. Once they key is compromised, security is lost.
The most popular and best known representative of this paradigm is DES.
DESxe2x80x94Digital Equipment Standard is the dominant Published cryptographic standard in the post World War II era. Until the late 70""s, Des and its variants were just about everything in publicly-exposed cryptography. The standard has been patched, enhanced, and augmented, and in its many implementations it is still the backbone of commercial cryptography, used throughout the global financial world, and elsewhere.
DES is clearly a computer-era extension of the classical ciphers. It""s designers appears to have asked themselves: how can we use the new tool, the electronic computer, to xe2x80x9ccookxe2x80x9d the age old transpositions and substitutions into such a complicated sequence that cryptanalysis will be prohibitive. DES raw input is any text file, or information sequence of any length, P, which is eventually encrypted into a cipher of equal length, C. The encryption is undertaken through a fixed size, relatively small, binary sequence, the key, k.
C=E(P,k)
Where E is the DES encryption algorithm. E is published, and has no secrets per se. The entire cryptanalytic strength of DES is hinged on the identify of the key k. DES is symmetric: its decryption key Kd equals its encryption key Ke (Ke=Kd=k). Thus the intended reader, would use k to produce:
P=D(C,k)
where D is the DES decryption algorithmxe2x80x94an exact reverse of the encryption process.
The original size key, as proposed by DES developers, (IBM), was 128 bits. When it became a standard it was reduced to 56 bits. As computers became more powerful, the size of the key inched up again. But at any rate, it is very small compared to the size of the encrypted message. This size variance pin points the cryptanalytic efforts on the identify of the keyxe2x80x94the weakest link.
DES security is based on the non-Bayesian assumption which says that checking i key-options out of a total of r key possibilities, will not modify the equal-likelihood of the remaining (r-i) key options, regardless of the choice or value of i. In other words, it would be necessary for a cryptanalyst to use the brute force approach: to check every possible key configuration. Accordingly one would assume that a cryptanalyst is privy to a plaintext and its cipher, and is using the fastest computers available to him for finding k, to be used for reading all other messages based on the same key. This assumption can be translated into time needed for a successful cryptanalysis based on knowledge of the computing power of the cryptanalyst. And in turn, this estimate allows for appraising the adequacy of a given key size.
The critical question with regard to DES security is the validity of the non-Bayesian assumption. The fact that DES was officially certified by the U.S. government, has only increased suspicion among many professionals, owing to the fact that it would be advantageous to certify a cipher which is strong enough to resist all cryptanalytic attacks, excepts those launched by the certifying authority.
On its face DES appears as a very arbitrary algorithm. It""s fundamentals have not changed over the years. This fact leads some to believe that the selected algorithm offers a trap door: a way for someone equipped with proper computing power and the right mathematical insight to find the desired key much faster than the nominal brute force attack.
DES is fully deterministic: the same input produces the very same output time and again. This fact opens an attack door by allowing small changes to the input stream, then monitoring the impact on the cipher. DES may be implemented through hardware, or through software, which is typically three orders of magnitude slower. DES Described: The input information to DES is first expressed in a binary form. The binary stream is divided into fixed size blocks, each containing 64 bits. Each block is then processed through the core DES operation to produce a 64 bit of cipher, using a 56 bits key. 
The encryption process is based on a succession of changes, (stages), each based on the result of the former. By order:
1. Key Independent Transposition
2. Key Dependent Bitwise Operations
3. Key Independent Transposition
The 64 input bits are processed through the key independent stage (1) above. Their output is processed through the key-dependent stage (2), and that output is processed through stage (3) above. All inputs and outputs are 64 bits long.
The key-independent transpositions simply switch locations of the input bits. The key dependent operations are several (the standard is 16) successive steps, each of the form:
1. Divide the 64 input bits to the leftmost 32 bit, L, and the rightmost 32 bits, R.
2. R will become the 32 leftmost bits in the output block.
3. L and R will be processed together with a derived key kxe2x80x2 The result is a
32 bits string which becomes the rightmost 32 bits in the output block. In detail: The derived key kxe2x80x2 is a string of 48 bits derived from the original 56 bits key. For each step in that stage, there is a different derived keyxe2x80x2.
The processing step in (3) above is as follows:
3.1. Expand R from 32 bits to 48 bit (Re), (by duplicating some bits based on their positions).
3.2. Combine kxe2x80x2 and Re in an Exclusive-Or Operation to create a new 48 bits string, O.
3.3. The 48 bits 0 string is then divided into 8 groups of 6 bits each.
3.4. Each 6 bits group is then processed through a position dependent process into a 4 bits block.
3.5. The 4-bits blocks are concatenated to form a 32 bits block, T
3.6. T is transposed to create a permutation thereof, Tp (32 bits).
3.7. Tp and L undergo an exclusive-or operation to yield a 32 bits string, which becomes the result of step 3 above.
The description above leaves a few implementation details unspecified, and that is in line with the variance of the various implementations. DES decryption works in reverse order.
Asymmetric Key Computing Era Cryptography
Since 1976, when Diffie and Hellman proposed the concept, the actual implementations thereof were based largely on mathematical operations which are easy to carry out one way, but not in the reverse. Such as:
1. Large numbers factoring
2. Discrete logarithms
3. Operation research (OR) problems
Many other mathematical cases where proposed, but they failed to attract popular application based on the previously mentioned fundamental implicit assumption. To use an asymmetric paradigm the cryptographer must be thoroughly convinced that exposing the encryption process will not betray the decryption phase. One can not guarantee that future mathematical insight, or that existing, but secret mathematical knowledge is not at a level that would render asymmetric crypto system practically vulnerable. Consequently, mathematicians, feel more comfortable with the above listed tracks which are based on problems that have been attacked for many years, and are still considered too difficult to solve, or say: have not yielded to fast solution insight.
The asymmetric public key algorithms follow the historic trend to employ Galois fields based on module arithmetics.
The most popular asymmetric method is analyzed below:
Large Numbers Factoring
Proposed in 1977 by Rivest, Shamir and Adelman, and known by the first letter of their narnes: RSA, this track works as follows:
Plaintext, P, is divided into blocks of size B. Each block B is encrypted using a pair of publicly available numbers (e,n). The resultant cipher is of size B (per block), and the encrypted blocks are concatenated to form the cipher C, corresponding to P.
C=E(P,e,n)
With P,e, and n in the open, security is based on the difficulty to reverse the encryption paradigm E, which is defined per block as:
c=be(mod n)
where b is the numeric value of any plaintext sequence of any block of size B in P, and c is the numeric value of the corresponding cipher sequence for that block.
A cryptanalyst will have to deduce b from knowledge of c,e, and n. Since there is no published formula, or accelerated method to extract b from the above formula, it is assumed that a cryptanalyst will have to essentially use a brute force approach. Hence by selecting e, and n large enough, the reverse encryption will become slow enough.
The intended reader will decrypt the cipher C, block by block. For each block:
b=cd(mod n)
where d is a secret number, large enough to frustrate brute-force analysis.
RSA system calls for finding two large numbers, e and d such that the above encryption and decryption can be implemented. e, and d ( and the corresponding n) are extracted from an obscure number theory theorem:
for any two numbers e, and d such that:
xe2x80x83ed=1 mod xcfx86(n)
it holds that for any b:
ti (be)d mod n=b
(n) is the number of numbers less than n, which are relatively prime to n.
Accordingly: if
c=be(mod n)
then:
b=cd(mod n)
which is exactly the RSA process. To prepare the system, the designer will have to identify a tuple (e,d,n) to fit these relationships. RSA inventors offered an algorithm for extracting such tuples at will. The security of their selection is based on the assumption that factoring large numbers is a very difficult and time consuming process.
RSA is typical in the sense that even the xe2x80x98easyxe2x80x99 mathematical operations are quite complicated, and as a result encrypting large files is time consuming and rather unwieldy.
Published Variety: All the above described categories (pseudo-random keys, short symmetric keys, and short asymmetric keys), have become target for an increasingly rich body of literature. By and large, most of these proposed algorithms remain a literary spectacle, with little application. The reason is fundamental: to certify, or even to recommend a given cryptographic algorithm, one must have spent considerable time trying to expose its weaknesses, if any. It""s difficult to find anyone to invest in such exhaustive mathematical analysis, for an algorithm that no one uses. It is a xe2x80x9cCatch-22xe2x80x9d syndrome: new algorithms do not become popular, before they are being xe2x80x9cblessedxe2x80x9d by the professional community. Alas, non-popular algorithms can hardly justify the pre-blessing process.
This rich variety and corresponding obscurity of cryptographic methods, may, on one hand lure savvy users who might assume that their predators would not suspect the use of an obscure algorithm. Alas, this lure is counterbalanced by the fear that once suspected, the employed algorithm would readily yield to a smart mathematician.
For the increasingly large community of cryptographic consumers, the choice is quite narrow: anything that is xe2x80x9cblessedxe2x80x9d by the mavens, and well xe2x80x9cpackagedxe2x80x9d by the sellers. And thus today we see the volume of sensitive financial data and its like being handled through DES, and its various variants, while the e-mail, and rogue users flock to PGP (Pretty Good Privacy). PGP: xe2x80x9cPretty Good Privacyxe2x80x9d is a well packaged hybrid product. It offers the advantage of RSA asymmetry, and the speed of DES-like file transmission (A non-US developed algorithm called IDEA). Two PGP users who have had no prior contact, and exchanged no secret information can initiate their contact by writing to each other through their respective, published public key (as described above). PGP then uses this initial contact to create a common symmetric key, which they both use from that point on.
PGP advantage is also its shortcoming. It allows two strangers to exchange sensitive information, without one really ascertaining the identify of the other.
Operational Status
While mathematical integrity is the heart of a wholesome cryptographic systemxe2x80x94its body is comprised of a slew of practical issues which must all be satisfied for the service to function. Cryptography is overhead, a burden. It must match the threat. If it does not, or if it is perceived as a mismatchxe2x80x94the effort would fail in the long run. That is so whether the cryptographic procedure is too meager, or too strict. Then there are the unintended side effects. Poor cryptography helps an opponent find what is sensitive and what is not. Overzealous cryptography has on some occasions locked the data even from its owner (e.g.: when keys are lost). Unlike television which offers its consumers good service regardless of their ignorance relative to the electronic technology that brings the picture to their living room, cryptography requires well trained users, to be effective. When only few used it, the training problem was limited. As it becomes a commodityxe2x80x94cryptographic education is of greater importance. And so is the need to establish cryptographic security on mathematics which is accessible to the multitude of non-professional mathematician, those who are intelligent laymen. Which is the edge that this invention emerges from.
Computer ushered in the so called information age. Most of what people do is increasingly expressed in computer files, and with it we all experience increased vulnerability to eavesdropping, and data theft, making encryption a necessary burden for many ordinary people. This transition from esoterica to main street brings with it fundamentally new demands which are yet to come. The need is much more pronounced in the coming age of intensive interconnectivity.
The Age of Mass-Interconnectivity: The Information Superhighway (The Internet)xe2x80x94a Prospective
The obscure and arcane art of cryptography is in the midst of a metamorphosis into an indispensable utility that would help render the Internet into a global repository, access, and communication of the full range of human data. The new need will inspire an unprecedented broadening of the offerings in product, technique and methodologies. The metamorphosis of cryptography will probably be emphasized through:
Dataship: Insuring Data Ownership on The Public Data Highway
First the premise: the Internet attracts so much growth that it has fast overtaken all its competitors with respect to public data traffic. Even the conversational phone system is now being sucked into the Internet bowls. Faxes which yesterday seemed to be the wave of the future, now give way to email, and its attachments. Large organizations have invested in building their own private communication networkxe2x80x94which now, too, lose traffic in favor of the public highway. Much as the automotive system is based not on private roads, but on public thoroughfares, so will the movement and parking of information.
However far a car travels, when stopped by a police officer, its identity, and ownership are readily exposed. Automotive theft is minuscule compared to the number of cars and the miles they log. And similarly for data: ownership, and protection should be firmly established.
Accordingly, one may paint a situation where data travels in functional packets comprised of: data payload, and data overhead. The former is the contents which is being transported from a sender to a receiver; the latter is all the data that is necessary for safe transportation of the payload.
It appears necessary to link the payload and the overhead in a tamper resistant, and accident resistant fashion. Without which the specter of data driven public disaster is way too real. If we had no locks, and no car and driver registration system, we would have had chaos where people drive whichever car they find on the parking lot.
The two questions that beg answers are:
1. How to fuse payload and overhead
2. What should be the contents of the overhead
Thumbnail answers follow.
Fusing (linking) data payload and data overhead. The key here seems to be data representation. The initial separation between the two parts should be eliminated by using products related to cryptography, which will create one data packet in a way that removing or chaining any part thereof will destroy both payload and overhead. In other words, it would be difficult to separate the two parts, and then somehow attach a new payload to the separated overhead, or vice versa.
About the contents of the overhead. Perhaps we can take a page from Mother nature: every single cell in our body carries in its DNA the full range of information necessary to rebuild the body as a whole. Ideally, the overhead data should tell as much as possible about the message: who sent it, to whom, and as part of what larger communication, or action it happens to be.
Daniel (alternatively written as DNL) is a cryptographic paradigm, featuring ease of matching many plaintexts of choice to any give cipher (the deniability property). Consequently, the cipher itself cannot betray the specific plaintext that generated it, as it is xe2x80x9clostxe2x80x9d in the large list of candidate plaintexts, all of which are decryption-generated from the ciphertext.
In the prevailing cryptographic methods, it is extremely difficult to match a given cipher with a plaintext of choice, thus insuring that the cipher points to the true plaintext. Security there, is hinged solely on the expected cryptanalytic effort.
Daniel also offers fine-tuned control of cryptanalytic effort, allowing it to increase above any set levelxe2x80x94as opposed to fixedxe2x80x94complexity per-paintext in prevailing techniques.
Daniel offers a ready capability to string and to nest messages into a single cipher, such that different readers would be able to read only messages and part-messages intended for their attention. This xe2x80x9cmessage-fusionxe2x80x9d option, offers unlimited levels of authentication, verification, and elaboration by managing who reads what in a single cipher.
Advantageously, the present invention can stimulate free, candid documentation of private, delicate and extremely sensitive communications. Private and public-interest personal histories, which may include embarrassment, illegalities and unethical conduct, and which today do not get documented owing to fear of loss or a legal discovery process will now expectedly be committed to writing and eventually be made part of our history.
Further, the present invention can help render the Internet as a truly publicly used framework, for the full range of human activities, regardless of their level of privacy. Today, the Internet is mostly a harbor for public data. Information for which there is a restriction of users, is still, by and large, kept outside the Internet. Having one more cryptographic instrument (Daniel) will help send private and semi-private information towards the Internet. Thereby information will increase its influence on public prosperity, convenience and welfare.
Deniability per se is not novel. The association of deniability with a practical cipher is unique. The unconditionally secure cipher system known as the one-time pad, or infinite key, offers full deniability. A one-time pad cipher C may be claimed to represent any same size plaintext of choice P, by simply selecting same size key K by XOR-ing (performing bit by bit exclusive-or operation), C and P. It is the impracticality of the one-time pad that casts a shadow on any claim that it was actually used, and that K is the key to reading C. The one-time pad deniability will work only for truly random keys. Once a pseudo-random mechanism is used, the deniability is void. Daniel, by contrast, offers deniability on grounds of nominal usefulness of its paradigm. Daniel may be employed as a bona-fide crypto system, offering straight forward security, efficiency and speed. And it is this usability factor that endows the deniability feature with its intriguing attraction.
Still other objects and advantages of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein the preferred embodiments of the invention are shown and described, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawings and description thereof are to be regarded as illustrative in nature, and not as restrictive.